Dynamic "Succincter"
December 4, 2024 (GHC 4405)

Abstract: The seminal work "Succincter" by Pătraşcu presents a way to store an augmented B-tree with only two bits of redundancy while supporting queries efficiently. It is a generic and powerful tool for designing static succinct data structures. We extend "Succincter" to support dynamic operations, achieving the same space bounds as the static "Succincter" and the optimal time bounds, enabling numerous applications. Our technique addresses a key challenge in dynamic succinct data structures: managing variable-size components within a contiguous piece of memory.